package com.leetcode.partition6;

import com.leetcode.common.TreeNode;

import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/20 10:53
 */
public class LC530二叉搜索树的最小绝对差 {

    public static int getMinimumDifference(TreeNode root) {
//        return recursion(root);
        return iteration(root);
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(100, new TreeNode(50, null, new TreeNode(80)), new TreeNode(119));
//        TreeNode root = new TreeNode(1, new TreeNode(0), new TreeNode(48, new TreeNode(12), new TreeNode(49)));
//        TreeNode root = new TreeNode(1, null, new TreeNode(5, new TreeNode(3), null));
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));
        System.out.println(getMinimumDifference(root));
    }

    //使用栈模拟中序遍历
    private static int iteration(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;
        int answer = Integer.MAX_VALUE;
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                s.push(cur);
                cur = cur.left;
                continue;
            }
            cur = s.pop();
            if (pre != null) answer = Math.min(answer, Math.abs(cur.val - pre.val));
            pre = cur;
            cur = cur.right;
        }
        return answer;
    }

    private static TreeNode pre = null;

    //通过记录当前节点的前驱节点进行中序递归
    private static int recursion1(TreeNode root) {
        if (root == null) return Integer.MAX_VALUE;
        int left = recursion1(root.left);       //左子树的最小绝对差
        int mid = Integer.MAX_VALUE;        //当前节点与前驱节点的最小绝对差与左子树的最小绝对差的最小值
        if (pre != null) mid = Math.min(left, Math.abs(root.val - pre.val));
        pre = root;
        int right = recursion1(root.right);     //寻找右子树的最小绝对差
        return Math.min(mid, right);
    }

    //通过找每个节点的前驱、后继进行后序递归
    private static int recursion(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return Integer.MAX_VALUE;
        //对于二叉搜索树，最小绝对差要么在根节点与前驱节点中发生，要么在根节点与后继节点中发生
        int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE;
        //递归寻找左子树的最小差
        if (root.left != null) left = recursion(root.left);
        //递归寻找右子树的最小差
        if (root.right != null) right = recursion(root.right);
        //当前结点与前驱和后继的绝对差
        TreeNode pre = predecessor(root);
        //注意：没有前驱或者后继的当前结点需要返回Integer.MAX_VALUE，如果返回了root.val，则会计算绝对差和最小结点的最小值
        int num1 = pre == null ? Integer.MAX_VALUE : Math.abs(root.val - pre.val);
        TreeNode suc = successor(root);
        int num2 = suc == null ? Integer.MAX_VALUE : Math.abs(root.val - suc.val);
        return Math.min(Math.min(num2, num1), Math.min(left, right));
    }

    private static TreeNode predecessor(TreeNode root) {
        if (root == null) return null;
        TreeNode res = root.left;
        if (res == null) return null;
        while (res.right != null) res = res.right;
        return res;
    }

    private static TreeNode successor(TreeNode root) {
        if (root == null) return null;
        TreeNode res = root.right;
        if (res == null) return null;
        while (res.left != null) res = res.left;
        return res;
    }
}
